/**
 * Copyright (c) 2010 Simple Graph Tools contributors. All rights reserved.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *   http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * $Id$
 */
package org.sgt.coredef.util;

import java.util.HashSet;
import java.util.Set;

import org.eclipse.emf.common.util.BasicEList;
import org.eclipse.emf.common.util.EList;
import org.sgt.coredef.Chain;
import org.sgt.coredef.Edge;
import org.sgt.coredef.Graph;
import org.sgt.coredef.Node;

/**
 * This is the default abstract implementation of a GraphWalkerPolicy, it must
 * be overridden by concrete implementations.
 * <UL>
 * <LI>the {@link #prettyPrint(Chain)}, methods prints chains in the following
 * form : <BR/>'StartNode'->'EndNode' : 'StartNode' ,/
 * + 'node' ... 'EndNode' <BR/>
 * if the Nodes are DescribedObjects, their name is printed, a comma is
 * separating two nodes which are not connected by an edge of this chain, a '+'
 * is separating two connected nodes</LI>
 * <LI>all other methods ensure that built chains:
 * <UL>
 * <LI>do not loop on start, end or any of their nodes</LI>
 * <LI>can not grow further when they have reached their start or end node</LI>
 * </UL>
 * </LI>
 * </UL>
 * 
 * @author Anne BUTTIGHOFFER
 * 
 */
public abstract class DefaultGraphWalkerPolicy implements IGraphWalkerPolicy {

	/**
	 * Returns a Set of Chains corresponding to all possibilities of growth in
	 * the backward direction of the given chain. The returned set is granted to
	 * be empty only if the {@link #canGrowBackwards(Chain, Graph)} method would
	 * return true.
	 * 
	 * @param seed
	 *            {@link Chain}
	 * @param graph
	 *            {@link Graph}
	 * @return Set of Chains representing the seed's growth possibilities
	 */
	public final Set<Chain> growBackwards(final Chain seed, final Graph graph) {
		Logger.log("Growing Backwards Chain :" + prettyPrint(seed));
		Set<Chain> chains = new HashSet<Chain>();
		EList<Node> graphNodes = graph.getNodes();
		EList<Edge> graphEdges = graph.getEdges();

		Node firstNode = ChainHelper.getFirstListedNode(seed);
		if (firstNode == null) {
			firstNode = seed.getEndNode();
		}

		if (firstNode == null) {
			return chains;
		}
		for (Edge prevEdge : firstNode.getIns()) {
			// Filtering out edges not included in Graph
			if (graphEdges.contains(prevEdge)) {
				Node prevNode = prevEdge.getSource();
				// Filtering out nodes not included in Graph
				// and avoiding loops
				if (graphNodes.contains(prevNode)
						&& !seed.getNodes().contains(prevNode)
						&& graph.getNodes().contains(prevNode)) {
					Chain newChain = ChainHelper.copy(seed);
					if (!newChain.getEdges().contains((prevEdge))
							&& !newChain.getNodes().contains(prevNode)) {
						newChain.getEdges().add(0, prevEdge);
						newChain.getNodes().add(0, prevNode);
						chains.add(newChain);
						Logger.log("Grown Chain :" + prettyPrint(newChain));
					}
				}
			}
		}
		return chains;
	}

	/**
	 * Returns a Set of Chains corresponding to all possibilities of growth in
	 * the forward direction of the given chain. The returned set is granted to
	 * be empty only if the {@link #canGrowForward(Chain, Graph)} method would
	 * return true.
	 * 
	 * @param seed
	 *            {@link Chain}
	 * @param graph
	 *            {@link Graph}
	 * @return Set of Chains representing the seed's growth possibilities
	 */
	public final Set<Chain> growForward(final Chain seed, final Graph graph) {
		Logger.log("Growing Froward Chain :" + prettyPrint(seed));
		Set<Chain> chains = new HashSet<Chain>();
		EList<Node> graphNodes = graph.getNodes();
		EList<Edge> graphEdges = graph.getEdges();

		Node finalNode = ChainHelper.getLastListedNode(seed);
		if (finalNode == null) {
			finalNode = seed.getStartNode();
		}

		if (finalNode == null) {
			return chains;
		}
		for (Edge nextEdge : finalNode.getOuts()) {
			// Filtering out edges not included in Graph
			if (graphEdges.contains(nextEdge)) {
				Node nextNode = nextEdge.getDestination();
				// Filtering out nodes not included in Graph
				// and avoiding loops (listedNodes + start)
				// connection to endNode handled below
				if (nextNode != seed.getEndNode()) {
					if (graphNodes.contains(nextNode)
							&& !seed.getNodes().contains(nextNode)
							&& seed.getStartNode() != nextNode) {
						Chain newChain = ChainHelper.copy(seed);
						if (!newChain.getEdges().contains(nextEdge)) {
							newChain.getEdges().add(nextEdge);
							newChain.getNodes().add(nextNode);
							chains.add(newChain);
							Logger.log("     " + prettyPrint(newChain));
						}
					}
				} else {
					Chain newChain = ChainHelper.copy(seed);
					if (!newChain.getEdges().contains(nextEdge)) {
						newChain.getEdges().add(nextEdge);
						chains.add(newChain);
						Logger.log("     " + prettyPrint(newChain));
					}
				}
			}
		}
		return chains;
	}

	/**
	 * Determines whether given chain, in the context of given graph, can be
	 * grown in the backward direction. If true is returned, a call to
	 * {@link #growBackward(Chain, Graph)} is granted to return 
	 * a non empty Set.<BR/>
	 * <BR/>
	 * <EM>Implementation : this method must grant that
	 * the first node as listed by {@link ChainHelper#getLastListedNode(Chain)}
	 * 	<UL>
	 * 		<LI>is at least the destination of one Edge contained 
	 * in the graph</LI>
	 * 		<LI>this edge has a node contained in the graph 
	 * as source</LI>
	 * 	</UL>
	 * </EM>
	 * 
	 * @param chain
	 *            {@link Chain}
	 * @param graph
	 *            {@link Graph}
	 * @return true only if chain growth is possible.
	 */
	public final boolean canGrowBackwards(final Chain chain
			, final Graph graph) {
		Node firstNode = ChainHelper.getFirstListedNode(chain);
		EList<Node> graphNodes = graph.getNodes();
		EList<Edge> graphEdges = graph.getEdges();
		if (firstNode == null) {
			Logger.logError("Null first node in chain :" + chain);
		}
		if (!graphNodes.contains(firstNode)) {
			Logger.logError("First node in chain :" + chain
					+ " does NOT belong to graph :" + graph);
		}
		EList<Edge> filtered = new BasicEList<Edge>();
		filtered.addAll(firstNode.getIns());
		for (Edge in : firstNode.getIns()) {
			if (!graphEdges.contains(in)) {
				filtered.remove(in);
			}
		}
		return !filtered.isEmpty();
	}

	/**
	 * Determines whether given chain, in the context of given graph, can be
	 * grown in the forward direction. If true is returned, a call to
	 * {@link #growForward(Chain, Graph)} is granted to return 
	 * a non empty Set.<BR/>
	 * <BR/>
	 * <EM>Implementation : this method must grant that
	 * the final node as listed by {@link ChainHelper#getLastListedNode(Chain)}
	 * 	<UL>
	 * 		<LI>is at least the source of one Edge contained in the graph</LI>
	 * 		<LI>this edge has a node contained in the graph as destination</LI>
	 * 	</UL>
	 * </EM>
	 * 
	 * @param chain
	 *            {@link Chain}
	 * @param graph
	 *            {@link Graph}
	 * @return true only if chain growth is possible.
	 */
	public final boolean canGrowForward(final Chain chain
			, final Graph graph) {
		Node finalNode = ChainHelper.getLastListedNode(chain);
		EList<Node> graphNodes = graph.getNodes();
		EList<Edge> graphEdges = graph.getEdges();
		if (finalNode == null) {
			Logger.logError("Null final node in chain :" + chain);
		}
		if (!graphNodes.contains(finalNode)) {
			Logger.logError("Final node in chain :" + chain
					+ " does NOT belong to graph :" + graph);
		}
		EList<Edge> filtered = new BasicEList<Edge>();
		filtered.addAll(finalNode.getOuts());
		for (Edge out : finalNode.getOuts()) {
			if (!graphEdges.contains(out)) {
				filtered.remove(out);
			}
			if (out.getDestination() == chain.getEndNode()
					&& chain.getEdges().contains(out)) {
				filtered.remove(out);
				// We have reached this chain's end.
				// No need to go further as long as we
				// do not handle loops.
				return false;
			}
		}
		return !filtered.isEmpty();
	}

	/**
	 * Returns a String representation of the given Chain suitable for user
	 * display.
	 * 
	 * @param chain
	 *            the {@link Chain} to represent.
	 * @return a string representation of Chain.
	 */
	public final String prettyPrint(final Chain chain) {
		return ChainHelper.stringRepresentation(chain);
	}
}
